﻿#region

using System.Text;

#endregion

namespace AdvancedTraining.Lesson47;

/// <summary>
/// N叉树的序列化和反序列化
/// LeetCode 428. Serialize and Deserialize N-ary Tree
/// 时间复杂度：O(N)，其中N是树中节点的数量
/// 空间复杂度：O(H)，其中H是树的高度，主要由递归栈深度决定
/// </summary>
public class SerializeAndDeserializeNaryTree //leetcode_0428
{
    /// <summary>
    /// 测试方法
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== N叉树序列化和反序列化测试 ===");

        // 测试用例1：示例案例
        Console.WriteLine("测试用例1：复杂N叉树");
        var root1 = BuildTestTree1();
        var serialized1 = Codec.Serialize(root1);
        var deserialized1 = Codec.Deserialize(serialized1);
        var reserialized1 = Codec.Serialize(deserialized1);

        Console.WriteLine($"原始序列化：{serialized1}");
        Console.WriteLine($"反序列化后序列化：{reserialized1}");
        Console.WriteLine($"序列化结果一致：{serialized1 == reserialized1}");
        Console.WriteLine($"通过：{(serialized1 == reserialized1 ? "是" : "否")}");
        Console.WriteLine();

        // 测试用例2：单节点树
        Console.WriteLine("测试用例2：单节点树");
        var root2 = new Node(42);
        var serialized2 = Codec.Serialize(root2);
        var deserialized2 = Codec.Deserialize(serialized2);
        var reserialized2 = Codec.Serialize(deserialized2);

        Console.WriteLine($"序列化结果：{serialized2}");
        Console.WriteLine($"序列化结果一致：{serialized2 == reserialized2}");
        Console.WriteLine($"通过：{(serialized2 == reserialized2 ? "是" : "否")}");
        Console.WriteLine();

        // 测试用例3：空树
        Console.WriteLine("测试用例3：空树");
        var serialized3 = Codec.Serialize(null);
        var deserialized3 = Codec.Deserialize(serialized3);
        var reserialized3 = Codec.Serialize(deserialized3);

        Console.WriteLine($"序列化结果：{serialized3}");
        Console.WriteLine($"序列化结果一致：{serialized3 == reserialized3}");
        Console.WriteLine($"通过：{(serialized3 == reserialized3 ? "是" : "否")}");
        Console.WriteLine();

        // 测试用例4：多层级树
        Console.WriteLine("测试用例4：多层级树");
        var root4 = BuildTestTree4();
        var serialized4 = Codec.Serialize(root4);
        var deserialized4 = Codec.Deserialize(serialized4);
        var reserialized4 = Codec.Serialize(deserialized4);

        Console.WriteLine($"序列化结果：{serialized4}");
        Console.WriteLine($"序列化结果一致：{serialized4 == reserialized4}");
        Console.WriteLine($"通过：{(serialized4 == reserialized4 ? "是" : "否")}");
        Console.WriteLine();

        // 测试用例5：只有子节点且无子节点的节点
        Console.WriteLine("测试用例5：兄弟节点");
        var root5 = BuildTestTree5();
        var serialized5 = Codec.Serialize(root5);
        var deserialized5 = Codec.Deserialize(serialized5);
        var reserialized5 = Codec.Serialize(deserialized5);

        Console.WriteLine($"序列化结果：{serialized5}");
        Console.WriteLine($"序列化结果一致：{serialized5 == reserialized5}");
        Console.WriteLine($"通过：{(serialized5 == reserialized5 ? "是" : "否")}");
    }

    /// <summary>
    /// 构建测试树1：复杂的N叉树结构
    ///     1
    ///   / | \
    ///  2  3  4
    /// / \
    ///5   6
    ///|
    ///7
    /// </summary>
    /// <returns>根节点</returns>
    private static Node BuildTestTree1()
    {
        var a = new Node(1);
        var b = new Node(2);
        var c = new Node(3);
        var d = new Node(4);
        var e = new Node(5);
        var f = new Node(6);
        var g = new Node(7);

        a.children.Add(b);
        a.children.Add(c);
        a.children.Add(d);
        b.children.Add(e);
        b.children.Add(f);
        e.children.Add(g);

        return a;
    }

    /// <summary>
    /// 构建测试树4：多层级复杂树
    ///     1
    ///   / | \
    ///  2  3  4
    /// / \    |
    ///5   6   7
    ///       / \
    ///      8   9
    /// </summary>
    /// <returns>根节点</returns>
    private static Node BuildTestTree4()
    {
        var root = new Node(1);
        var node2 = new Node(2);
        var node3 = new Node(3);
        var node4 = new Node(4);
        var node5 = new Node(5);
        var node6 = new Node(6);
        var node7 = new Node(7);
        var node8 = new Node(8);
        var node9 = new Node(9);

        root.children.Add(node2);
        root.children.Add(node3);
        root.children.Add(node4);

        node2.children.Add(node5);
        node2.children.Add(node6);

        node4.children.Add(node7);
        node7.children.Add(node8);
        node7.children.Add(node9);

        return root;
    }

    /// <summary>
    /// 构建测试树5：只有兄弟节点
    ///    1
    ///  / | \
    /// 2  3  4
    /// </summary>
    /// <returns>根节点</returns>
    private static Node BuildTestTree5()
    {
        var root = new Node(1);
        var node2 = new Node(2);
        var node3 = new Node(3);
        var node4 = new Node(4);

        root.children.Add(node2);
        root.children.Add(node3);
        root.children.Add(node4);

        return root;
    }

    /// <summary>
    /// N叉树节点类
    /// 注意：这个类仅用于测试，不提交到在线判题系统
    /// </summary>
    public class Node
    {
        /// <summary>
        /// 子节点列表
        /// </summary>
        public List<Node> children;

        /// <summary>
        /// 节点值
        /// </summary>
        public int val;

        /// <summary>
        /// 默认构造函数
        /// </summary>
        public Node()
        {
            children = new List<Node>();
        }

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="_val">节点值</param>
        public Node(int _val)
        {
            val = _val;
            children = new List<Node>();
        }

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="_val">节点值</param>
        /// <param name="_children">子节点列表</param>
        public Node(int _val, List<Node> _children)
        {
            val = _val;
            children = _children;
        }
    }

    /// <summary>
    /// N叉树编解码器类
    /// 这是需要提交到在线判题系统的类
    /// 序列化格式：val1,[,val2,val3,],val4,[,val5,],...
    /// 其中[]表示子树的开始和结束
    /// </summary>
    public class Codec
    {
        /// <summary>
        /// 将N叉树序列化为字符串
        /// 序列化格式：节点值，然后如果有子节点，用[]包围子节点的序列化结果
        /// 例如：1,[2,[5,7,],6,],3,4,
        /// </summary>
        /// <param name="root">根节点</param>
        /// <returns>序列化字符串</returns>
        public static string Serialize(Node root)
        {
            if (root == null)
                // 空树！直接返回#
                return "#";
            var builder = new StringBuilder();
            Serial(builder, root);
            return builder.ToString();
        }

        /// <summary>
        /// 序列化辅助方法
        /// 当前来到head节点，递归序列化
        /// </summary>
        /// <param name="builder">字符串构建器</param>
        /// <param name="head">当前节点</param>
        private static void Serial(StringBuilder builder, Node head)
        {
            builder.Append(head.val + ",");
            if (head.children.Count > 0)
            {
                builder.Append("[,");
                foreach (var next in head.children) Serial(builder, next);
                builder.Append("],");
            }
        }

        /// <summary>
        /// 从字符串反序列化为N叉树
        /// 处理空树和正常树的序列化数据
        /// </summary>
        /// <param name="data">序列化字符串</param>
        /// <returns>根节点</returns>
        public static Node Deserialize(string data)
        {
            if (data.Equals("#")) return null;
            var splits = data.Split(",");
            var queue = new LinkedList<string>();
            foreach (var str in splits) queue.AddLast(str);
            return Deserial(queue);
        }

        /// <summary>
        /// 反序列化辅助方法
        /// 使用队列来按顺序处理节点信息
        /// </summary>
        /// <param name="queue">包含待处理节点信息的队列</param>
        /// <returns>当前节点</returns>
        private static Node Deserial(LinkedList<string> queue)
        {
            var temp = queue.First();
            queue.RemoveFirst();
            var cur = new Node(Convert.ToInt32(temp));
            cur.children = new List<Node>();
            if (queue.Count > 0 && queue.First.Value.Equals("["))
            {
                queue.RemoveFirst();
                while (!queue.First.Value.Equals("]"))
                {
                    var child = Deserial(queue);
                    cur.children.Add(child);
                }

                queue.RemoveFirst();
            }

            return cur;
        }
    }
}